|
In number theory, the ''n''th Pisano period, written π(''n''), is the period with which the sequence of Fibonacci numbers taken modulo ''n'' repeats. For example, the Fibonacci numbers modulo 3 are , 1, 1, 2, 0, 2, 2, 1, 0, 1, 1, 2, 0, 2, 2, 1, etc., with the first eight numbers repeating, so π(3) = 8. Pisano periods are named after Leonardo Pisano, better known as Fibonacci. The existence of periodic functions in Fibonacci numbers was noted by Joseph Louis Lagrange in 1774.〔〔(On Arithmetical functions related to the Fibonacci numbers ). ''Acta Arithmetica'' XVI (1969). Retrieved 22 September 2011.〕 == Tables == The first Pisano periods and their cycles (with spaces before the zeros for readability) are: Onward the Pisano periods are 10, 24, 28, 48, 40, 24, 36, 24, 18, 60, 16, 30, 48, 24, 100, 84, 72, 48, 14, 120, 30, 48, 40, 36, 80, 24, 76, 18, 56, 60, 40, 48, 88, 30, 120, 48, 32, 24, 112, 300, ... For ''n'' > 2 the period is even, because alternatingly ''F''(''n'')2 is one more and one less than ''F''(''n'' − 1)''F''(''n'' + 1) (Cassini's identity). If ''n'' = ''F'' (2''k'') (''k'' > 1), then π(''n'') = 4''k''; If ''n'' = ''F'' (2''k'' + 1) (''k'' > 1), then π(''n'') = 8''k'' + 4. That is, if the modulo base is a Fibonacci number (>=3) with an even index, the period is twice the index. If the base is a Fibonacci number (>=5) with an odd index, the period is 4 times the index. The period is relatively small, 4''k'' + 2, for ''n'' = ''F'' (2''k'') + ''F'' (2''k'' + 2), i.e. Lucas number ''L'' (2''k'' + 1), with ''k'' a positive integer. This is because ''F''(−2''k'' − 1) = ''F'' (2''k'' + 1) and ''F''(−2''k'') = −''F'' (2''k''), and the latter is congruent to ''F''(2''k'' + 2) modulo ''n'', showing that the period is a divisor of 4''k'' + 2; the period cannot be 2''k'' + 1 or less because the first 2''k'' + 1 Fibonacci numbers from 0 are less than ''n''. The second half of the cycle, which is of course equal to the part on the left of 0, consists of alternatingly numbers ''F''(2''m'' + 1) and ''n'' − ''F''(2''m''), with ''m'' decreasing. Furthermore, the period is 4''k'' for ''n'' = ''F''(2''k''), and 8''k'' + 4 for ''n'' = ''F''(2''k'' + 1). The number of occurrences of 0 per cycle is 1, 2, or 4. Let ''p'' be the number after the first 0 after the combination 0, 1. Let the distance between the 0s be ''q''. *There is one 0 in a cycle, obviously, if ''p'' = 1. This is only possible if ''q'' is even or ''n'' is 1 or 2. *Otherwise there are two 0s in a cycle if ''p''2 ≡ 1. This is only possible if ''q'' is even. *Otherwise there are four 0s in a cycle. This is the case if ''q'' is odd and ''n'' is not 1 or 2. For generalized Fibonacci sequences (satisfying the same recurrence relation, but with other initial values, e.g. the Lucas numbers) the number of occurrences of 0 per cycle is 0, 1, 2, or 4. Also, it can be proven that :π''k''(''n'') ≤ 6''n'', with equality if and only if ''k'' is odd, ''k''2 + 4 is squarefree, and ''n'' = 2 · (''k''2 + 4)''r'', for ''r'' ≥ 1, the first examples for ''k'' = 1 being ''π''1(10) = 60 and ''π''1(50) = 300. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Pisano period」の詳細全文を読む スポンサード リンク
|